Shortest Unsorted Continuous Subarray

问题描述（难度简单-581）

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

1
2
3

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

方法一：sort+循环

直接复制一个数组出来，排序完了之后比较排序和非排序数组。时间复杂度O(NlogN)，空间复杂度O(N)。

package P581;

import java.util.Arrays;

/**
 * @autor yeqiaozhu.
 * @date 2019-10-15
 */
public class SortSolution {
    public int findUnsortedSubarray(int[] nums) {
        int[] copy=Arrays.copyOf(nums,nums.length);
        Arrays.sort(copy);
        int i=0,j=nums.length-1,shortest=0;
        while (i<j){
            if (nums[i]==copy[i]) {
                i++;
            }
            if (nums[j]==copy[j]) {
                j--;
            }
            if (nums[i]!=copy[i] && nums[j]!=copy[j]) {
                shortest=j-i+1;
                break;
            }
        }
        return shortest;
    }

    public static void main(String[] args) {
        int[] ints={1,2,3,4};
        new SortSolution().findUnsortedSubarray(ints);
    }
}

方法二：两边遍历

从前往后找到比前面最大值还要小的值，从后往前找到比之前最小值还要大的值，即为边界值。时间复杂度O(N),空间复杂度O(1)。

package P581;

/**
 * 两次遍历
 * 遍历的过程中保存最大值和最小值
 * 判断当前的值大于这个最大值的时候就是end位置
 * 判断当前的值小于这个最小值的时候就是begin位置
 * @autor yeqiaozhu.
 * @date 2019-10-15
 */
public class UsingOneCircle {
    public int findUnsortedSubarray(int[] nums) {
        int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
        int end=-1;int begin=0;
        for (int i = 0; i < nums.length; i++) {
            max=Math.max(max,nums[i]);
            if (nums[i]<max) {
                end=i;
            }
        }

        for (int j = nums.length-1; j >=0; j--) {
            min=Math.min(min,nums[j]);
            if (nums[j]>min) {
                begin=j;
            }
        }
        return end-begin+1;
    }

    public static void main(String[] args) {
        int[] ints={5,4,3,2,1};
        System.out.println(new UsingOneCircle().findUnsortedSubarray(ints));
    }
}

问题描述（难度简单-581）

方法一：sort+循环

方法二：两边遍历

总结